// https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
// 
// 题干：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。


// 示例：
// 输入：head = [1,2,3,4,5] n = 2     输出：[1,2,3,5]

// 碎语：怎么求倒数第K个节点？

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution
{
public:
    ListNode* removeNthFromEnd(ListNode* head, int n)
    {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto slow = dummy, fast = head;

        while (n--)
        {
            fast = fast->next;
        }

        while (fast != nullptr)
        {
            slow = slow->next;
            fast = fast->next;
        }

        auto del = slow->next;
        auto next = del->next;

        slow->next = next;

        return dummy->next;
    }
};

int main()
{
    auto dummy = new ListNode(-1);
    auto cur = dummy;

    for (int i = 1; i <= 5; i++)
    {
        cur->next = new ListNode(i);
        cur = cur->next;
    }


    auto rhead = Solution().removeNthFromEnd(dummy->next, 2);

    while (rhead)
    {
        cout << rhead->val << " ";
        rhead = rhead->next;
    }
    cout << endl;

    return 0;
}